JCF（java集合框架）

? ? 接口interfaces

a.Collection接口說明

b.Map接口說明

2.類class

棧和隊列：

都是線性表操作的子類

1.棧(Stack)LIFO:

a.順序棧（基于數組）（數組末尾添加和刪除元素即可）

b.鏈式棧（基于鏈表）

? ? ? ?核心操作:push pop peek

2.隊列(Queue)FIFO：

a.鏈式隊列（基于鏈表）

b.順序隊列——循環隊列

? ? ? ?核心操作:offer poll peek

3.雙端隊列（Deque）:LinkedList

? ? ??
二叉樹

1.前身：樹：度 葉子結點 父節點 子節點 層次 高度深度 分支節點

樹的表示形式：

Class Node{

? ? ? ?Int value;

? ? ? ?Node firstChild

? ? ? ?Node nextBrother

}

? ? 特點：每個節點最多有兩顆子樹，即二叉樹不存在度大于2的結點

二叉樹的子樹有左右之分，其子樹的次序不能顛倒，因此二叉樹是有序樹

? ? 特殊的二叉樹{ 滿二叉樹 完全二叉樹}
? ? 性質：1.第i層上最多有2^（i-1）

2.深度K最大的結點數2^k-1

3.n0=n2+1;

4.n個結點完全二叉樹深度為log2(n+1)

5.存儲：順序存儲

? ? ? ? ? ? ?鏈式存儲：a。孩子表示法

? ? ? ? ? ? ? ? ? ? ? ? ? b.孩子雙親表示法

6.遍歷{前序 中序 后序}

7. 基本操作{preorderTraversal

InOrderTraversal

PostOrderTraversal

GetSize

GetLeafSize

getLevelSize}
堆（heap）

優先級隊列——入隊一樣，出隊不一樣，按照優先級出隊

普通隊列：FIFO

? ? 概念：堆是一顆完全二叉樹（結構上）
? ? 從節點值的要求

? ? 最大堆：根節點的值一定不小于左右子樹
? ? 最小堆：根節點的值一定不大于左右子樹

? ? 堆的實現：（基本都是基于二叉樹——二叉堆）

***最大堆—》根節點>=左右子樹

? ? ? ? ? ? ? ? ? ? 層次和節點的大小沒有任何關系***

相同數據可以構建成多種類型的堆（最大&最小）

? ? 堆的表示——(數組)

堆的三大核心操作 ? //add(val)向堆中添加元素 siftUp(元素上浮)

? ? ? ? ? ? ? ? ? ? ? ? ? ?//ectractMax():取出最大堆 siftDown(元素下沉)

? ? ? ? ? ? ? ? ? ? ? ? ? //heapify 將任意一個數組堆化 add +siftDown

****原地堆排序*** ?O（nlogn）

? ? 將任意數組heapify（siftDown） 調整為最大堆
? ? 調整最大值與數組末尾的位置（siftDown 與之前不同：不考慮已交換元素）